
//1203.项目管理
class Solution {
    vector<int> topologicalSort(vector<int>& prev,vector<vector<int>>& back,int sz)  
    {
        vector<int> ret;
        queue<int> q;    //记录可以做的项目或小组
        for(int i=0;i<sz;i++)  if(!prev[i]) q.push(i);

        while(q.size())
        {
            int n=q.size();
            for(int i=0;i<n;i++)
            {
                int x=q.front();
                q.pop();
                ret.push_back(x);
                for(auto& a:back[x]) 
                    if(--prev[a]==0) q.push(a);
            }
        }
        return ret.size()==sz?ret:vector<int>();
    }
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        for(auto&x: group) if(x==-1) x=m++;   //将-1的小组带上编号

        vector<int> prev_grp(m);                 //记录每个小组前置的小组个数
        vector<vector<int>> back_grp(m);         //记录每个小组后面的小组
        vector<int> prev_item(n);                //记录每个项目的前置项目
        vector<vector<int>> back_item(n);        //记录每个项目后面的项目
        for(int i=0;i<n;i++)
        {
            int g=group[i];              //所属组
            auto& nums=beforeItems[i];   //前置项目
            prev_item[i]=nums.size();    //前置项目的个数
            if(nums.size())  
            {
                set<int> s;
                for(auto& obj:nums)
                {
                    back_item[obj].push_back(i);      //i项目在ojb项目的后面
                    int prev=group[obj];              //前置项目的所属组
                    if(!s.count(prev)&&prev!=g)
                    {
                        prev_grp[g]++;
                        back_grp[prev].push_back(g);
                    }    
                    s.insert(prev);
                }
            }
        }
        vector<int> grp=topologicalSort(prev_grp,back_grp,m);
        vector<int> itm=topologicalSort(prev_item,back_item,n);
        if(grp.empty()||itm.empty()) return {};

        vector<int> ans;
        //将小组中项目的先后顺序进行整合
        vector<vector<int>> each_obj(m);
        for(auto& it:itm)
            each_obj[group[it]].push_back(it);
        for(auto& g:grp)
            ans.insert(ans.end(),each_obj[g].begin(),each_obj[g].end());

        return ans;
    }
};